import java.util.Arrays;

/**
 * @description:
 * @Author: wuzhenbin
 * @CreateTime: 2025/2/16
 */
public class leetcode_34 {
    public static void main(String[] args) {
        int[] ints = {5, 7, 7, 8, 8, 10};
        //int[] ints = {1};
        System.out.println(Arrays.toString(searchRange(ints, 8)));
    }

    public static int[] searchRange(int[] nums, int target) {

        return binarySearch(nums, 0, nums.length - 1, target);
    }

    private static int[] binarySearch(int[] nums, int left, int right, int target) {
        // 二分查找循环
        while (left <= right) {
            int mid = left + (right - left) / 2;  // 防止溢出

            if (nums[mid] == target) {
                int[] ints = new int[2];
                int tmpleft = mid;
                int tmpright = mid;
                while (tmpleft > 0 && nums[tmpleft-1] == target) {
                    tmpleft--;
                }
                while (tmpright < nums.length-1 && nums[tmpright+1] == target) {
                    tmpright++;
                }
                ints[0] = tmpleft;
                ints[1] = tmpright;
                return ints;
            } else if (nums[mid] > target) {
                right = mid - 1;  // 目标值在左半边
            } else {
                left = mid + 1;  // 目标值在右半边
            }
        }

        // 如果未找到目标值，left 即为目标值应该插入的位置
        return new int[]{-1,-1};
    }
}
